501. Черный ящик

Черный ящик представляет собой примитивное хранилище данных, способное содержать в себе целые числа. Черный ящик также имеет специальную переменную i. Изначально ящик пуст, а i = 0. Над черным ящиком можно производить следующие операции:

add(x): положить элемент x в черный ящик;

get: увеличить i на 1 и вернуть i - ый наименьший элемент, хранящийся в черном ящике;

Рассмотрим работу черного ящика на примере:

шаг	операция	i	содержимое черного ящика	результат
1	add(3)	0	3
2	get	1	3	3
3	add(1)	1	1, 3
4	get	2	1, 3	3
5	add(-4)	2	-4, 1, 3
6	add(2)	2	-4, 1, 2, 3
7	add(8)	2	-4, 1, 2, 3, 8
8	add(-1000)	2	-1000, -4, 1, 2, 3, 8
9	get	3	-1000, -4, 1, 2, 3, 8	1
10	get	4	-1000, -4, 1, 2, 3, 8	2
11	add(2)	4	-1000, -4, 1, 2, 2, 3, 8

Моделирование работы черного ящика можно описать двумя массивами:

1) A[1], A[2], …, A[m] – последовательность, хранящаяся в черном ящике. Для выше приведенного примера A = {3, 1, -4, 2, 8, -1000, 2}.

2) u[1], u[2], …, u[n] – последовательность, описывающая количество элементов в черном ящике при выполнении операций get. В примере u = {1, 2, 6, 6}.

Вход. Первая строка содержит количество тестов k. Каждый тест содержит числа m, и n (n £ m £ 30000), A[1], …, A[m], u[1], …, u[n].

Выход. Для каждого теста вывести результаты, которые будет выдавать черный ящик после выполнения каждой операции get. Между тестами выводить пустую строку.

Пример входа

1

7 4

3 1 -4 2 8 -1000 2

1 2 6 6

Пример выхода

3
3
1
2

РЕШЕНИЕ

структуры данных

Анализ алгоритма

Задача красиво решается при помощи структуры данных multiset. Занесем в пустое мультимножество s макимальный элемент и установим на него указатель iter. Заносим в мультимножество числа последовательности A[i]. Если текущее заносимое число A[i] меньше того, на которое указывает iter, то уменьшаем iter на 1. Иначе iter остается без изменения. С выводом каждого числа u[i] увеличиваем iter на 1. Таким образом iter постоянно указывает на элемент, возвращаемый при операции get.

Реализация алгоритма

Последовательность чисел A[1], …, A[m], которая заносится в черный ящик, храним в массиве mas. Черный ящик хранится в переменной s типа мультимножество.

int mas[30001];

multiset<int> s;

multiset<int>::iterator iter;

Основной цикл программы. Читаем количество тестов tests.

scanf("%d",&tests);

while(tests--)

{

Обнуляем черный ящик s для каждого теста. Читаем входные данные.

s.clear();

scanf("%d %d",&m,&n);

for(i = 0; i < m; i++) scanf("%d",&mas[i]);

Занесем в s максимальное число для удобства его дальнейшего использования. Установим указатель iter на начало черного ящика – минимальный элемент, хранящийся в нем. В переменной ptr храним количество чисел, занесенных в черный ящик.

s.insert(2100000000);

iter = s.begin(); ptr = 0;

for(i = 0; i < n; i++)

{

Вводим значение u[i]. Для вывода результата на очередной запрос get, необходимо просто вывести значение, на которое указывает iter. Но при этом в черном ящике должно находиться u[i] чисел. Если до этого в ящик было занесено менее u[i] чисел (ptr < u), то заносим их последовательно, уменьшая на 1 указатель iter каждый раз когда очередное значение m[ptr] меньше того, на которое указывает iter.

scanf("%d",&u);

while(ptr < u)

{

s.insert(mas[ptr++]);

if (mas[ptr-1] < *iter) iter--;

}

printf("%d ",*iter);iter++;

}

printf("\n");

}